package com.LeeCode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 删除子字符串的最大得分
 */

public class Code1717 {
    public static void main(String[] args) {
        String s = "paaaabdbabfbybbbtaaab";
        int x = 5, y = 4;
        System.out.println(new Code1717().maximumGain(s, x, y));
    }


    public int maximumGain(String s, int x, int y) {
        //记录字符a和b出现的次数
        int ac = 0, bc = 0, res = 0;
        char[] cs = s.toCharArray();
        for (char c : cs) {
            //如果不是a或b说明字符被隔开了 要计算剩余的得分略小的可能 并将ab数量清零
            if (c != 'a' && c != 'b') {
                //剩下的a和b只能组成得分较小的情况
                res += Math.min(ac, bc) * Math.min(x, y);
                ac = 0;
                bc = 0;
            } else if (c == 'a') {
                if (x > y) {//ab得分大时，优先保存a尽量和后面的b组成ab
                    ac++;
                } else {//ba得分大时，贪心和前面的b组合成ba
                    if (bc != 0) {
                        bc--;
                        res += y;
                    } else ac++;
                }
            } else if (c == 'b') {
                if (x > y) {//ab得分大时，贪心和前面的a组合成ab
                    if (ac != 0) {
                        ac--;
                        res += x;
                    } else bc++;
                } else {//ab得分大时,优先保存b尽量和后面的a组成ba
                    bc++;
                }
            }
        }
        //最后可能存在剩余较小值没有计算的情况，补充计算
        res += Math.min(ac, bc) * Math.min(x, y);
        return res;
    }


    public int maximumGain1(String s, int x, int y) {
        boolean removeABFirst = x >= y;
        char first = removeABFirst ? 'a' : 'b';
        char second = removeABFirst ? 'b' : 'a';
        int highScore = Math.max(x, y);
        int lowScore = Math.min(x, y);

        int totalScore = 0;
        StringBuilder sb = new StringBuilder(s);

        // 第一步：删除高分组合
        totalScore += removeAndCount(sb, first, second, highScore);
        // 第二步：删除低分组合
        totalScore += removeAndCount(sb, second, first, lowScore);

        return totalScore;
    }

    private int removeAndCount(StringBuilder s, char first, char second, int score) {
        Deque<Character> stack = new ArrayDeque<>();
        int totalScore = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == second && !stack.isEmpty() && stack.peek() == first) {
                stack.pop();
                totalScore += score;
            } else {
                stack.push(c);
            }
        }

        // 重构字符串
        s.setLength(0);
        while (!stack.isEmpty()) {
            s.append(stack.pollLast());
        }

        return totalScore;
    }


}
